//
// Created by madison on 2022/7/10.
//

#include "stack"

using namespace std;

/**
 * Definition for singly-linked list.
 **/
struct ListNode {
    int val;
    ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    // 方法一：计算链表长度
    int getLength(ListNode *head) {
        int length = 0;
        while (head) {
            ++length;
            head = head->next;
        }
        return length;
    }

    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummy = new ListNode(0, head);
        int length = getLength(head);
        ListNode *cur = dummy;
        for (int i = 1; i < length - n + 1; ++i) {
            cur = cur->next;
        }
        cur->next = cur->next->next;
        ListNode *ans = dummy->next;
        delete dummy;
        return ans;
    }

    // 方法二：栈
    ListNode *removeNthFromEnd1(ListNode *head, int n) {
        ListNode *dummy = new ListNode(0, head);
        stack<ListNode *> stk;
        ListNode *cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode *prev = stk.top();
        prev->next = prev->next->next;
        ListNode *ans = dummy->next;
        delete dummy;
        return ans;
    }

    // 方法三：双指针
    ListNode *removeNthFromEnd2(ListNode *head, int n) {
        ListNode *dummy = new ListNode(0, head);
        ListNode *first = head;
        ListNode *second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode *ans = dummy->next;
        delete dummy;
        return ans;
    }
};

int main() {
    ListNode *node4 = new ListNode(5);
    ListNode *node3 = new ListNode(4, node4);
    ListNode *node2 = new ListNode(3, node3);
    ListNode *node1 = new ListNode(2, node2);
    ListNode *head = new ListNode(1, node1);

    ListNode *temp = head;
    while (temp) {
        printf("%d\t", temp->val);
        temp = temp->next;
    }

    printf("\n");
    Solution solution;
    head = solution.removeNthFromEnd2(head, 3);
    ListNode *temp1 = head;
    while (temp1) {
        printf("%d\t", temp1->val);
        temp1 = temp1->next;
    }
    return 0;
}